//#include<iostream>
//#include<queue>
//#include<unordered_map>
//using namespace std;
//unordered_map<string, int>d;
//queue<string>q;
//int dx[] = { -1,0,1,0 };
//int dy[] = { 0,1,0,-1 };
//int bfs(string star)
//{
//	string end = "12345678x";
//	d[star] = 0;
//	q.push(star);
//	while (q.size()) {
//		string t = q.front();
//		q.pop();
//		int distance = d[t];
//		if (t == end) {
//			return distance;
//		}
//		int k = t.find('x');
//		for (int i = 0; i < 4; i++) {
//			int a = dx[i] + k / 3;
//			int b = dy[i] + k % 3;
//			if (a >= 0 && a < 3 && b >= 0 && b < 3) {
//				swap(t[k], t[a * 3 + b]);
//				if (!d.count(t)) {
//					q.push(t);
//					d[t] = distance + 1;
//				}
//				swap(t[k], t[a * 3 + b]);
//			}
//		}
//	}
//	return -1;
//}